\documentclass[oneside]{homework} %%Change `twoside' to `oneside' if you are printing only on the one side of each sheet.

\studname{Ran Yu}
\studmail{ry2239@columbia.edu}
\coursename{Natural Language Processing}
\hwNo{2}
\uni{ry2239}

\usepackage{graphicx}
\usepackage{subfigure}
\begin{document}
\maketitle

\section*{Problem 1}
a) Here we introduce new rules and new non-terminals to solve the problem.\\
For the PCFG G', which has a set of rules R which take one of the two following forms:
\begin{itemize}
\item $X \to Y_1Y_2\dots Y_n~ for~X\in N,~n\geq2,~and~\forall i,~Y_i\in N.$
\item $X~\to Y~for~X\in N~and~Y\in N.$
\end{itemize}
To transform it into an 'equivalent' PCFG G' in Chomsky normal form, we introduce new rule: \begin{itemize}
\item'$X\to Z_1~for~X\in N~and~Z_1\in N$'
\end{itemize}
 to take the place of $X \to Y_1Y_2\dots Y_n~ for~X\in N,~n\geq2,~and~\forall i,~Y_i\in N$, and $p(X\to Z_1)=p(X\to Y_1Y_2\dots Y_n)$. And then introduce new non-terminals '$Z_2,~Z_3,\dots Z_{n-2}$' to bring in the new rules:
\begin{itemize}
\item $Z_1\to Y_2Z_2~for~Z_1\in N~and~Z_2\in N~and~Y_2\in N$
\item $Z_2\to Y_3Z_3~for~Z_2\in N~and~Z_3\in N~and~Y_3\in N$
\item \dots
\item $Z_{n-2}\to Y_{n-1}Y_n~for~Y_{n-1},~Y_n\in N$
\end{itemize}
And for the all new rules above, $p(Z_i\to Y_{i+1}Z_{i+1})=1.0$. In this way, under the new rules, the $p(X\to Y_1Y_2\dots Y_n)$ stay still.\\
b) After applied the new rules to the G'.\\
$~~~~$
\begin{tabular}{|l|l|}
\hline
$S\to NP~~VP$ & 0.7\\
\hline
$S\to NP~~NVP$ & 0.3\\
\hline
$NVP\to NP~~VP$ & 1.0\\
\hline
$VP\to Vt~~NP$ & 0.8\\
$VP \to Vt~~NPP$ &0.2\\
\hline
$NPP\to NP~ ~PP$ &1.0\\
\hline
$NP\to DT~~NNN$ & 0.3\\
$NP\to NP~~PP$ &0.7\\
\hline
$NNN\to NN~~NN$&1.0\\
\hline
$PP\to P~~NP$ & 1.0\\
\hline
\end{tabular} $~~~~~~~~~$
\begin{tabular}{|l|l|}
\hline
$Vt\to~saw$&1\\
\hline
$NN\to~man$&0.7\\
$NN\to~woman$&0.2\\
$NN\to~telescope$&0.1\\
\hline
$DT\to~the$&1.0\\
\hline
$IN\to~with$&0.5\\
$IN\to~in$&0.5\\
\hline
\end{tabular}
\section*{Problem 2}
a) The PCFG that Clarissa derive from the treebank is:\\\\
\begin{tabular}{|l|l|}
\hline
$S\to NP~VP$&1.0 \\
\hline
$VP\to V1~SBAR$&0.33\\
$VP\to VP~ADVP$&0.33\\
$VP\to V2$&0.33\\
\hline
$SBAR\to COMP~S$&1.0\\
\hline
\end{tabular}
$~~~~~$
\begin{tabular}{|l|l|}
\hline
$NP\to Fred$&0.17\\
$NP\to John$&0.17\\
$NP\to Sally$&0.32\\
$NP\to Bill$&0.17\\
$NP\to Jeff$&0.17\\
\hline
$V1\to said$&0.33\\
$V1\to declared$&0.33\\
$V1\to pronounced$&0.33\\
\hline
$V2\to snored$&0.33\\
$V2\to ran$&0.33\\
$V2\to swam$&0.33\\
\hline
$ADVP\to loudly$&0.33\\
$ADVP\to elegantly$&0.33\\
$ADVP\to quickly$&0.33\\
\hline
\end{tabular}
\\\\
b) The parse trees show as below,
\begin{figure}[!h]
     \centering  
     \subfigure[tree-1]{ \includegraphics[width=6cm, height=6cm]{p21.jpg}}
     \subfigure[tree-2]{ \includegraphics[width=6cm, height=6cm]{p22.jpg}}
 \end{figure}\\
 The probability of 'tree-1': $1.0^4\times 0.17^2\times 0.33^6=0.00003732$\\
 The probability of 'tree-2': $1.0^4\times 0.17^2\times 0.33^6=0.00003732$\\
 c) We solve the problem by introducing new rules and new non-terminal into the grammar.\\$~~~~~$
 \begin{tabular}{|l|l|}
\hline
$S\to NP~VP$&0.5 \\
$S\to NP~NVP$&0.5\\
\hline
$VP\to VP~ADVP$&0.5\\
$VP\to V2$&0.5\\
\hline
$NVP\to V1~SBAR$&1.0\\
\hline
$SBAR\to COMP~S$&1.0\\
\hline
\end{tabular}
$~~~~~$
\begin{tabular}{|l|l|}
\hline
$NP\to Fred$&0.17\\
$NP\to John$&0.17\\
$NP\to Sally$&0.32\\
$NP\to Bill$&0.17\\
$NP\to Jeff$&0.17\\
\hline
$V1\to said$&0.33\\
$V1\to declared$&0.33\\
$V1\to pronounced$&0.33\\
\hline
$V2\to snored$&0.33\\
$V2\to ran$&0.33\\
$V2\to swam$&0.33\\
\hline
$ADVP\to loudly$&0.33\\
$ADVP\to elegantly$&0.33\\
$ADVP\to quickly$&0.33\\
\hline
\end{tabular}\\
And the treebank transform to:\\
\begin{figure}[!h]
     \centering  
     \subfigure[tree-1]{ \includegraphics[width=5cm, height=5cm]{p23a.jpg}}
     \subfigure[tree-2]{ \includegraphics[width=5cm, height=5cm]{p23b.jpg}}
     \subfigure[tree-2]{ \includegraphics[width=5cm, height=5cm]{p23c.jpg}}
 \end{figure}\\
\section*{Problem 3}
a) The recursive part should be:\\
\begin{displaymath}
\pi(1,j,X)=\max_{X\to YZ \in R~j\in\{2,n\}}q(X\to YZ)\times\pi(1,j-1,Y)\times\pi(j,j,Z)
\end{displaymath}
The left-branching tree split into 2 sub-tree, one is $l-1$ the other one is the right-most word. And for that the tree is left-branching, so we do not need to calculate all the $\pi(i,j,X)$, every $\pi$ except $\pi(i,i,X)$ would be the style of $\pi(1,j,X)$. Therefore, we simply calculate the $\pi$s of $\pi(1,j,X)$.
\end{document}